#include <bits/stdc++.h>
using ll=long long;
using namespace std;
// int h,a,H,A;
// int t;
// int main()
// {
//     int sum=0;
//     cin>>t;
//     while(t--)
//     {
//         cin>>h>>a>>H>>A;
//         if(a>=H)cout<<-1<<endl;
//         else
//         {
//             //杀死一只毛球怪需要几次攻击
//             int m=(H/a)+(H%a==0?0:1);
//             int x=A*(m-1);//我扣除多少血
//             cout<<(h/x)+(h%x==0?-1:0)<<endl;
//         }
//     }
//     return 0; 
// }

//https://www.nowcoder.com/questionTerminal/9fbb4d95e6164cd9ab52e859fbe8f4ec
//对容器还是使用少了，没想到哈希表可以这么用
// int n;
// int main()
// {
//     cin>>n;
//     unordered_map<string,int> hashl;
//     string s[n];
    
//     for(int i=0;i<n;i++)
//     {
//         cin>>s[i];
//         sort(s[i].begin(),s[i].end());
//         hashl[s[i]]++;
//     }

//     cout<<hashl.size()<<endl;
//     return 0; 
// }


// class Solution {
//     public:
//         int count=0;
//         void dfs(vector<vector<int>>&m,vector<bool>&visit,int i)
//         {
//             visit[i]=true;
//             for(int j=0;j<m.size();j++)
//             {
//                 if(!visit[j]&&m[i][j]==1)
//                     dfs(m,visit,j);
//             }
//         }
//         int citys(vector<vector<int> >& m) {
//             int n=m.size();
//             vector<bool> visit(n,false);
//             for(int i=0;i<n;i++)
//             {
//                 for(int j=0;j<n;j++)
//                 {
//                     if(!visit[j]&&m[i][j]==1)
//                     {
//                         count++;
//                         dfs(m,visit,i);
//                     }
//                 }
//             }
//             return count;
//         }
//     };
// class Solution {
//     public:
//     void dfs(vector<vector<int>>&m,vector<bool>&vis,int i,int n)
//     {
//         vis[i]=true;
//         for(int j=0;j<n;j++)if(m[i][j]==1&&!vis[j])dfs(m,vis,j,n);
//     }
//     int citys(vector<vector<int> >& m) {
//         int n=m.size();
//         int count=0;
//         vector<bool> vis(n,false);
//         for(int i=0;i<n;i++)
//         {
//             if(!vis[i])
//             {
//                 count++;
//                 dfs(m,vis,i,n);
//             }
//         }
//         return count;
//     }
// };
class Solution 
{
public:    
    void bfs(vector<vector<int>>&m,vector<bool>& vis,int i)
    {
        //将当前点加入队列，并标记当前城市为访问过
        queue<int> q;
        q.push(i);
        vis[i]=true;
        while(!q.empty())
        {
            //取出队头元素，并去遍历和它相连通的城市
            int curr=q.front();
            q.pop();
            for(int j=0;j<m[curr].size();j++)
            {
                if(!vis[j]&&m[curr][j]==1)
                {
                    q.push(j);
                    vis[j]=true;
                }
            }
        }
    }
    int citys(vector<vector<int> >& m) 
    {
        int n=m.size();
        int count=0;
        vector<bool> vis(n,false);
        for(int i=0;i<n;i++)
        {
            //这是从点开始搜索的，只要当前点没有被访问过，就是一个城市群
            if(!vis[i])
            {
                count++;
                bfs(m,vis,i);
            }
        }
        return count;
    }
};